package org.example;

import java.util.*;

public class RandomizedSet {
    //变长数组+哈希实现，哈希可以实现O(1)的插入和移除，但是无法实现随机的一个，而数组则可以通过随机下标
    //来实现
    List<Integer> list;
    Map<Integer,Integer> map;
    Random random;
    public RandomizedSet() {
        list = new ArrayList<>();
        map = new HashMap<>();
        random = new Random();
    }

    public boolean insert(int val) {
        if (map.get(val) == null) {
            list.add(val);
            map.put(val,list.size() - 1);
            return true;
        }
        return false;
    }

    public boolean remove(int val) {
        Integer index = map.get(val);
        if (index != null) {
            int last = list.get(list.size() - 1);
            list.set(index,last);
            list.remove(list.size() - 1);
            map.put(last,index);
            map.remove(val);
            return true;
        }
        return false;
    }

    public int getRandom() {
        int rand = random.nextInt(list.size());
        return list.get(rand);
    }

    public static void main(String[] args) {
        RandomizedSet randomizedSet = new RandomizedSet();
        System.out.println(randomizedSet.insert(1));
        System.out.println(randomizedSet.remove(2));
        System.out.println(randomizedSet.insert(2));
        System.out.println(randomizedSet.getRandom());
        System.out.println(randomizedSet.remove(1));
        System.out.println(randomizedSet.insert(2));
        System.out.println(randomizedSet.getRandom());
    }
}
